package leetcode.匹配;

/**
 * todo 通配符匹配
 * <p>
 * https://leetcode-cn.com/problems/wildcard-matching/
 * <p>
 * 和剑指offer的19题：正则表达式匹配很相似
 * <p>
 * 动态规划和贪心：找状态转移方程
 * <p>
 * https://leetcode-cn.com/problems/wildcard-matching/solution/dong-tai-gui-hua-dai-zhu-shi-by-tangweiqun/
 */
public class Test44通配符匹配 {
    /*
     状态 dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配 (true 的话表示匹配)
     状态转移方程：
          1. 当 s[i] == p[j]，或者 p[j] == ? 那么 dp[i][j] = dp[i - 1][j - 1];
          2. 当 p[j] == * 那么 dp[i][j] = dp[i][j - 1] || dp[i - 1][j]    其中：
                dp[i][j - 1] 表示 * 代表的是空字符，例如 ab, ab*
                dp[i - 1][j] 表示 * 代表的是非空字符，例如 abcd, ab*
     初始化：
          1. dp[0][0] 表示什么都没有，其值为 true
          2. 第一行 dp[0][j]，换句话说，s 为空，与 p 匹配，所以只要 p 开始为 * 才为 true
          3. 第一列 dp[i][0]，当然全部为 false
    */
    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        // 状态 dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 初始化
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';
        }

        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') { // 遇到 * 号考虑两种情况：*代表空字符以及*代表多个字符
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }

        // 返回结果
        return dp[m][n];

    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "*"));
    }

    public boolean isMatch2(String s, String p) {
        int iStar = -1, jStar = -1, m = s.length(), n = p.length(), i = 0, j = 0;
        while (i < m) {
            if (j < n && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                i++;
                j++;
            } else if (j < n && p.charAt(j) == '*') {
                iStar = i;
                jStar = j;
                j++;
            } else if (iStar >= 0) {
                i = ++iStar;
                j = jStar + 1;
            } else {
                return false;
            }
        }
        while (j < n && p.charAt(j) == '*')
            j++;
        return j == n;
    }
}
